#include <cmath>
#include <cstring>
#include <string>
using namespace std;
struct control {
    int ct, val;
    control(int Ct, int Val = -1)
        : ct(Ct)
        , val(Val)
    {
    }
    inline control operator()(int Val)
    {
        return control(ct, Val);
    }
} _endl(0), _prs(1), _setprecision(2);
struct FastIO {
#define IOSIZE 1000000
    char in[IOSIZE], *p, *pp, out[IOSIZE], *q, *qq, ch[20], *t, b, K, prs;
    FastIO()
        : p(in)
        , pp(in)
        , q(out)
        , qq(out + IOSIZE)
        , t(ch)
        , b(1)
        , K(6)
    {
    }
    ~FastIO()
    {
        flush();
    }
    void flush()
    {
        fwrite(out, 1, q - out, stdout);
        q = out;
    }
    inline char getch()
    {
        return p == pp && (pp = (p = in) + fread(in, 1, IOSIZE, stdin), p == pp) ? b = 0, EOF : *p++;
    }
    inline void putch(char x)
    {
        q == qq && (fwrite(out, 1, q - out, stdout), q = out), *q++ = x;
    }
    inline void puts(const char str[])
    {
        fwrite(out, 1, q - out, stdout), fwrite(str, 1, strlen(str), stdout), q = out;
    }
    inline void getline(string& s)
    {
        s = "";
        for (char ch; (ch = getch()) != '\n' && b;)
            s += ch;
    }
#define indef(T)                                               \
    inline FastIO& operator>>(T& x)                            \
    {                                                          \
        x = 0;                                                 \
        char f = 0, ch;                                        \
        while (!isdigit(ch = getch()) && b)                    \
            f |= ch == '-';                                    \
        while (isdigit(ch))                                    \
            x = (x << 1) + (x << 3) + (ch ^ 48), ch = getch(); \
        return x = f ? -x : x, *this;                          \
    }
    indef(int) indef(long long) inline FastIO& operator>>(char& ch)
    {
        return ch = getch(), *this;
    }
    inline FastIO& operator>>(string& s)
    {
        s = "";
        char ch;
        while (isspace(ch = getch()) && b)
            ;
        while (!isspace(ch) && b)
            s += ch, ch = getch();
        return *this;
    }
    inline FastIO& operator>>(double& x)
    {
        x = 0;
        char f = 0, ch;
        double d = 0.1;
        while (!isdigit(ch = getch()) && b)
            f |= (ch == '-');
        while (isdigit(ch))
            x = x * 10 + (ch ^ 48), ch = getch();
        if (ch == '.')
            while (isdigit(ch = getch()))
                x += d * (ch ^ 48), d *= 0.1;
        return x = f ? -x : x, *this;
    }
#define outdef(_T)                                            \
    inline FastIO& operator<<(_T x)                           \
    {                                                         \
        !x && (putch('0'), 0), x < 0 && (putch('-'), x = -x); \
        while (x)                                             \
            *t++ = x % 10 + 48, x /= 10;                      \
        while (t != ch)                                       \
            putch(*--t);                                      \
        return *this;                                         \
    }
    outdef(int) outdef(long long) inline FastIO& operator<<(char ch)
    {
        return putch(ch), *this;
    }
    inline FastIO& operator<<(const char str[])
    {
        return puts(str), *this;
    }
    inline FastIO& operator<<(const string& s)
    {
        return puts(s.c_str()), *this;
    }
    inline FastIO& operator<<(double x)
    {
        int k = 0;
        this->operator<<(int(x));
        putch('.');
        x -= int(x);
        prs && (x += 5 * pow(10, -K - 1));
        while (k < K)
            putch(int(x *= 10) ^ 48), x -= int(x), ++k;
        return *this;
    }
    inline FastIO& operator<<(const control& cl)
    {
        switch (cl.ct) {
        case 0:
            putch('\n');
            break;
        case 1:
            prs = cl.val;
            break;
        case 2:
            K = cl.val;
            break;
        }
        return *this;
    }
    inline operator bool()
    {
        return b;
    }
} io;
#include <bits/stdc++.h>
#define mid ((tr[p].l + tr[p].r) >> 1)
using namespace std;
int fa[2000005], a[2000005], cnt[2000005], ans[2000005];
int find(int x)
{
    if (x == fa[x])
        return x;
    return fa[x] = find(fa[x]);
}
struct f {
    int l, r, id;
} b[2000005];
bool cmp(f x, f y) { return x.r < y.r; }
struct f1 {
    int l, r, ans, add;
} tr[2000005 * 4];
void wei(int p) { tr[p].ans = min(tr[p * 2].ans, tr[p * 2 + 1].ans); }
void jianshu(int p, int l, int r)
{
    tr[p].l = l, tr[p].r = r;
    if (l == r) {
        tr[p].ans = INT_MAX;
        return;
    }
    jianshu(p * 2, l, mid), jianshu(p * 2 + 1, mid + 1, r);
    wei(p);
}
void wei1(int p, int k)
{
    tr[p].ans = k - tr[p].r + 1;
    tr[p].add = k;
}
void chuan(int p)
{
    wei1(p << 1, tr[p].add), wei1(p << 1 | 1, tr[p].add);
    tr[p].add = 0;
}
void xiugai1(int p, int l, int r, int k)
{
    if (tr[p].l >= l && tr[p].r <= r) {
        wei1(p, k);
        return;
    }
    if (tr[p].add)
        chuan(p);
    if (l <= mid)
        xiugai1(p << 1, l, r, k);
    if (r > mid)
        xiugai1(p << 1 | 1, l, r, k);
    wei(p);
}
int cha(int p, int l, int r)
{
    if (tr[p].l >= l && tr[p].r <= r) {
        return tr[p].ans;
    }
    if (tr[p].add)
        chuan(p);
    int ans = INT_MAX;
    if (l <= mid)
        ans = min(ans, cha(p << 1, l, r));
    if (r > mid)
        ans = min(ans, cha(p << 1 | 1, l, r));
    return ans;
}
signed main()
{
    freopen("destory.in", "r", stdin);
    freopen("destory.out", "w", stdout);
    int n, m;
    io >> n >> m;
    int q;
    io >> q;
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= m; i++) {
        int x, y;
        io >> x >> y;
        fa[find(x)] = find(y);
    }
    for (int i = 1; i <= n; i++) {
        a[i] = find(i);
    }
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    for (int i = 1; i <= q; i++) {
        io >> b[i].l >> b[i].r;
        b[i].id = i;
    }
    sort(b + 1, b + 1 + q, cmp);
    jianshu(1, 1, n);
    int l = 1;
    for (int i = 1; i <= n; i++) {
        xiugai1(1, cnt[a[i]] + 1, i, i);
        fa[cnt[a[i]]] = cnt[a[i]] + 1;
        cnt[a[i]] = i;
        while (l <= q && b[l].r == i) {
            ans[b[l].id] = cha(1, b[l].l, find(b[l].l));
            l++;
        }
    }
    for (int i = 1; i <= q; i++) {
        io << ans[i] << '\n';
    }
    io.flush();
    return 0;
}
